//
//  FindRepeatNumber.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/7/19.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  剑指 Offer 03. 数组中重复的数字

import UIKit

/*
 剑指 Offer 03. 数组中重复的数字

 找出数组中重复的数字。


 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

 示例 1：

 输入：
 [2, 3, 1, 0, 2, 5, 3]
 输出：2 或 3
  

 限制：

 2 <= n <= 100000
 */

class FindRepeatNumber: NSObject {
    
    //LeetCode提交耗时432ms
    func findRepeatNumber(_ nums: [Int]) -> Int {

        var checkNums:[Int:Bool] = [:]
        
        for n in nums{
            if checkNums[n] == true{
                return n
            }else{
                checkNums[n] = true
            }
        }
        return -1
    }
    
    
    //此解法直接报超时  因此contains()确实非常耗时
    func findRepeatNumber2(_ nums: [Int]) -> Int {

        var checkNums:[Int] = []
        
        for n in nums{
            if checkNums.contains(n){
                return n
            }else{
                checkNums.append(n)
            }
        }
        return -1
    }
    
    
    //先排序再查找，重复的肯定是前后挨着的
    //同样耗时 412ms
    func findRepeatNumber3(_ nums: [Int]) -> Int {
        let nums = nums.sorted()
        for i in 1 ... nums.count-1{
            if nums[i] == nums[i-1] {
                return nums[i]
            }
        }
        return -1
    }
    
    
    //原地置换。
    /*
     根据题目中的条件  在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内
     可得知：如果该数组为有序，那么数字n必定在数组中下标为i的位置。
     利用这一个条件，我们从头扫描，如果下标为n的元素值缺不等于n而等于m，那么我们就把m和数组中下标为m的值进行交换，交换过程中如果遇到了n=m，则我们就找到了重复的元素
     该方法提交耗时396ms
     */
    func findRepeatNumber4(_ nums: [Int]) -> Int {
        
        var nums = nums
        
        var tmp = -1
        
        for i in 0 ... nums.count - 1{
            while (nums[i] != i) {
                if nums[i] == nums[nums[i]] {
                    return nums[i]
                }else{
                    tmp = nums[i]
                    
                    nums[i] = nums[tmp]
                    
                    nums[tmp] = tmp
                }
            }
        }
        
        return -1
    }
}
